package com.searchtree.twofourtree;

import java.util.ArrayList;

import com.searchtree.main.Utilities;
import com.searchtree.tree.*;

public class TwoFourTree extends AbstractTree {

	private static TwoFourTree twoFourTree;
	private TwoFourTreeNode rootNode;

	private TwoFourTree() {
		super();
	}

	public static TwoFourTree getInstance() {
		if (twoFourTree == null) {
			twoFourTree = new TwoFourTree();
		}
		return twoFourTree;
	}

	/**
	 * Adds a node to the twoFourTree
	 * 
	 * @param String
	 *            key, the value of the node to be added
	 */
	@Override
	public void addNode(String key) {
		// Is there an RootNode?
		if (this.rootNode == null) {
			rootNode = new TwoFourTreeNode(key);
		} else {
			boolean added = false;
			TwoFourTreeNode previousNode = null;
			TwoFourTreeNode n = rootNode;

			while (!added) {
				// Overflow
				if (n.isFourNode()) {
					TwoFourTreeNode leftNode = new TwoFourTreeNode(
							n.getLeftKey(), n.getChildren().get(0), n
									.getChildren().get(1));
					TwoFourTreeNode rightNode = new TwoFourTreeNode(
							n.getRightKey(), n.getChildren().get(2), n
									.getChildren().get(3));

					// Overflow in the rootNode
					if (previousNode == null) {
						rootNode = new TwoFourTreeNode(n.getMiddleKey());
						rootNode.addChild(leftNode);
						rootNode.addChild(rightNode);
						n = rootNode;

					}
					// Overflow in another node
					else {
						previousNode.addKey(n.getMiddleKey());
						previousNode.addChild(leftNode);
						previousNode.addChild(rightNode);
						n = previousNode;

					}
				}

				previousNode = n;

				if (n.childrenAreLeafNodes()) {
					n.addKey(key);
					added = true;

				} else {
					ArrayList<String> keys = n.getKeys();
					for (int i = 0; i < keys.size(); i++) {
						String keyFromN = keys.get(i);
						if (Utilities.compareStringValues(key, keyFromN) == -1) {
							n = (TwoFourTreeNode) n.getChildren().get(i);
							break;
						} else if ((Utilities
								.compareStringValues(key, keyFromN) == 1)
								&& (i == keys.size() - 1)) {
							n = (TwoFourTreeNode) n.getChildren().get(i + 1);
							break;
						} else if (Utilities.compareStringValues(key, keyFromN) == 0) {
							added = true;
							break;
						}
					}
				}

			}
		}
	}

	/**
	 * Start call of the recursive searchNode method. Calls the searchNode
	 * method with the rootNode as startingpoint.
	 * 
	 * @param String
	 *            key, the key to be searched
	 */
	@Override
	public AbstractNode searchNode(String key) {
		return searchNode(key, this.rootNode);
	}

	/**
	 * Recursive method to search a 2-4 Node containing the key given
	 * 
	 * @param String
	 *            key, the String to be searched. AbstractNode n, the node in
	 *            which to search for the key.
	 * @return AbstractNode n, the node containing the key
	 */
	@Override
	protected AbstractNode searchNode(String key, AbstractNode n) {
		if (n instanceof LeafNode) {
			return n;
		} else {
			ArrayList<String> keys = ((TwoFourTreeNode) n).getKeys();
			for (int i = 0; i < keys.size(); i++) {
				String keyFromN = keys.get(i);
				int decide = Utilities.compareStringValues(key, keyFromN);
				if (decide == -1) {
					n = this.searchNode(key, ((TwoFourTreeNode) n)
							.getChildren().get(i));
					break;
				} else if (decide == 1 && (i == keys.size() - 1)) {
					n = this.searchNode(key, ((TwoFourTreeNode) n)
							.getChildren().get(i + 1));
					break;
				}
			}
			return n;
		}
	}

	/**
	 * Searches the key an generates a message
	 * 
	 * @param String
	 *            key
	 * @return String message
	 */
	public String searchKey(String key) {
		AbstractNode n = searchNode(key);
		if (n instanceof LeafNode) {
			return "The searchterm: " + key
					+ "can not be found in this binaryTree";
		} else {
			TwoFourTreeNode bsn = (TwoFourTreeNode) (n);
			if((bsn.getKeys().size() > 1 && bsn.getKeys().get(0).equals(key) &&  bsn.getKeys().get(1).equals(key))){
				return"The searchterm: " + key
						+ " can not be found in this binaryTree";
			}
			return "The key " + key + " has been found in this 2-4 Tree.\n"
					+ bsn.toString();
		}
	}

	/**
	 * Returns the rootNode of the 2-4 Tree
	 * 
	 * @Return rootNode, The rootNode of the binary search tree
	 */
	@Override
	public TwoFourTreeNode getRootNode() {
		return this.rootNode;
	}

}
